\section{Introduction}

This project is the final project of the second year of the Bachelor programme
in Artificial Intelligence at the University of Amsterdam. This paper is the
result of four students working together for one month on a specific AI problem.

Playing computer games has become ever more popular. Computer games have an
important advantage over traditional games: when there are no friends or other
people around to play with you, you can sometimes play them against a virtual
player whose behaviour is determined by the computer. Developing these
characters is hard and time consuming.

Last year a couple of students came up with the idea of enhancing the
intelligence of such a computer player (often called a 'bot') using
\textit{genetic algorithms}. They opted to do this in the 3D First Person
Shooter \textit{Quake 3 Arena}, because the developers of the game, Id Software,
released the source under \textit{GPL} and Quake 3 already had the facilities to
have bots play the game. In four weeks they got Quake 3 Arena running
on some of the computers at the university which were running the Linux
operating system. They then implemented a simplistic version of a
\textit{genetic algorithm}. Their supervisor wanted a new set of students to 
improve the project, and we did just that.


\section{Theory}
\label{theory}

The use of the biological terms \textit{genotype} and \textit{phenotype} has
been expanded upon by other authors. The genotype is the coded representation of
an individual, their characteristics. Examples in our context would be a gene
that determines whether a bot is very speedy, its accuracy etc.
Genetic algorithms typically use populations of the genotypes
consisting of binary strings or value parameters. These are then interpreted to produce
phenotypes. These phenotypes determine the outer appearance of the genotypes, which is then 
evaluated to some fitness criteria.
In our case, bots could be evaluated using the number of other bots or players
they killed, how many times they died, what rank they received after a round was
over, etc. After such a fitness evaluation, individuals are selected for
reproduction. New genotypes are created by applying cross-over and mutation operators
on the genotyes of the individuals with the best
results of the evaluation. After this cycle repeats (many times) you would
ideally get a population with much improved genotype values.

\section{Research Question}
\label{research_question}

% This stuff still needs a lot of work.
Based on the principles outlined in section \ref{theory}, we are going to
construct and implement a genetic algorithm in Quake 3 Arena. This should
produce bots that continuously get better as their speed, aim
and other characteristics improve due to the evolutionary process.

Of course, raising all such genotypes to their maximum causing them to be
"perfect" is not very interesting. During the four weeks, we attempted to investigate
two main research questions:

\begin{enumerate}
\item
What is the effect of genotype to phenotype mapping choices on the evolution,
in particular on the search/fitness-space?
\item
What does the emergence of specific niche populations say about the shape
of the search space?
\end{enumerate}

The answers to these questions both have to do with what is often referred to as
the \textit{fun-factor}. The idea behind the fun-factor is that it is no fun
whatsoever to play against a perfect opponent, because humans (by their very
nature) make mistakes. It would therefore be preferable to have a computer
opponent who makes similar (amounts of) mistakes. 
\begin{quote}
"\textit{Adaptive game AI can improve the entertainment
value of games by allowing computer-controlled opponents to fix weaknesses
automatically in the game AI, and to respond to changes in human-player
tactics.}" (Marc Ponsen, Hector Munoz-Avila, Pieter Spronck \& David W. Aha, 
ref. \ref{reference1})
\end{quote}
Having such an environment, where your computer opponent is matched to your 
skills so as to provide interesting and satisfactory gameplay is said to 
increase the fun-factor. Clearly having a bot that can be fast, accurate and 
good at dodging your shots all at the same time is not going to be all that 
much fun, whereas playing against a bot that is only a bit of each, or focuses 
on one of those characteristics would be much more fun. \footnote{Note that the 
characteristics used here are examples, Quake III Arena actually uses a much 
more extensive and versatile set of characteristics} In the same way, having a 
bot that focuses on jumping a lot in a level with a low ceiling will have a low 
fun-factor, just like having a bot that never jumps will not do much good to the 
fun-factor of a game in a level with lots of wide open spaces separated by gaps 
(which a player would normally have to jump across).

